// 连续子数组的最大和

int maxSubArray(vector<int>& nums) {
        int maxSum=nums[0];
        int res=nums[0];
        for(int i=1;i<static_cast<int>(nums.size());i++)
        {
            maxSum=std::max(maxSum+nums[i],nums[i]);

            res=std::max(maxSum,res);

        }
        return res;
    }
	

// 将一维数组转换为二维数组

vector<vector<int>> construct2DArray(vector<int>& original, int m, int n) {
        if(original.size()!=m*n)
            return vector<vector<int>>();

        vector<vector<int>> vv;

        int index=0;

        for(int i=0;i<m;i++)
        {   
            vv.push_back(vector<int>());
            for(int j=0;j<n;j++)
            {
                vv[i].push_back(original[index++]);
            }
        }

        return vv;
    }

// 用栈操作构建数组

   vector<string> buildArray(vector<int>& target, int n) {
        
        vector<string> vS;

        int x=1;

        int i=0;

        while(i<static_cast<int>(target.size()))
        {
            if(target[i]==x)
            {
                vS.push_back("Push");
                i++;
            }
            else
            {
                vS.push_back("Push");
                vS.push_back("Pop");
            }
            x++;
        }
        return vS;
    }

// 省份数量

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {

        int n=(int)isConnected.size();
        
        vector<int> ufs(n,-1);

        auto u= [&] (int x,int y) mutable
        {   
            while(ufs[x]>0)
            {
                x=ufs[x];
            }
            while(ufs[y]>0)
            {
                y=ufs[y];
            }

            if(x==y)
                return;

            ufs[x]+=ufs[y];
            ufs[y]=x;
        };

        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(isConnected[i][j]==1)
                {
                    u(i,j);
                }
            }
        }

        int count=0;
        for(auto e : ufs)
        {
            if(e<0)
                count++;
        }

        return count;
    }
};